package com.yeung.swordoffer;

import java.util.ArrayList;

/**
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 */
public class 平衡二叉树 {
    public boolean IsBalanced_Solution(TreeNode root) {
        //1. 先判断 是不是二叉搜索树(利用中序遍历)
        ArrayList<Integer> list = new ArrayList<>();
        if (verityTree(list)) {
            //是二叉搜索树
            //2.  判断是不是平衡树, 通过树高
            return isBalanced(root);
        }
        return false;

    }


    private boolean isBalanced(TreeNode root) {
        if (root != null) {
            if (Math.abs(getDeepth(root.left) - getDeepth(root.right)) > 1) {
                return false;
            } else {
                isBalanced(root.left);
                isBalanced(root.right);
            }
        }
        return true;
    }

    public void Order(TreeNode root, ArrayList<Integer> list) {
        if (root == null) return;
        Order(root.left, list);
        list.add(root.val);
        Order(root.right, list);
    }

    public boolean verityTree(ArrayList<Integer> list) {
        boolean flag = true;
        for (int i = 0; i < list.size() - 2; i++) {
            if (list.get(i) > list.get(i + 1)) {
                flag = false;
                break;
            }

        }
        return flag;
    }

    public int getDeepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDeepth(root.left);
        int right = getDeepth(root.right);
        return Math.max(left, right) + 1;
    }

}
